#ifndef _MERGESORT_H
#define _MERGESORT_H

template <typename T>
int Merge(T arr[],int p,int q,int r)
{
    int invnum=0;
    int Ln=q-p+1;
    int Rn=r-q;
    int n=r-p+1;
    T *Larr=new T[Ln];
    T *Rarr=new T[Rn];
    for(int i=0;i<Ln;i++)
        Larr[i]=arr[p+i];
    for(int i=0;i<Rn;i++)
        Rarr[i]=arr[q+1+i];

    int li=0,ri=0;
    int index=p;
    for(;li<Ln && ri<Rn;)
    {
        if(Larr[li]<=Rarr[ri])
            arr[index++]=Larr[li++];
        else
        {
            invnum+=(Ln-li);
            arr[index++]=Rarr[ri++];
        }
    }
    if(ri<Rn)
    {
        for(int i=ri;i<Rn;i++)
            arr[index++]=Rarr[i];
    }
    else if(li<Ln)
    {
        for(int i=li;i<Ln;i++)
        {
            arr[index++]=Larr[i];
        }
    }

    delete[] Larr;
    delete[] Rarr;

    return invnum;
}

template <typename T>
int MergeSort(T arr[],int p,int r)
{
    if(p<r)
    {
        int num=0;
        int q=(p+r)/2;
        num+=MergeSort(arr,p,q);
        num+=MergeSort(arr,q+1,r);
        num+=Merge(arr,p,q,r);
        return num;
    }
    else
        return 0;
}

template <typename T>
int GetInvNum(T arr[],int n)
{
    int invnum=0;
    for(int i=0;i<n-1;i++)
    {
        for(int j=i;j<n;j++)
        {
            if(arr[i]>arr[j])
                invnum++;
        }
    }
    return invnum;
}

#endif